# -*- coding: utf-8 -*-


# 简单选择排序
def select_sort(array):
    n = len(array)
    for i in range(0, n):
        min_index = i
        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]


def heapify(array, n, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    # 如果比当前跟元素大，记录位置
    if left < n and array[largest] < array[left]:
        largest = left
    if right < n and array[largest] < array[right]:
        largest = right
    if largest != i:
        array[largest], array[i] = array[i], array[largest]
        heapify(array, n, largest)


# 堆排序
def heap_sort(array):
    n = len(array)
    for i in range((n - 1) // 2, -1, -1):
        heapify(array, n, i)
    for i in range(n - 1, 0, -1):
        array[0], array[i] = array[i], array[0]
        heapify(array, i, 0)


arr = [16, 7, 3, 20, 17, 8]
heap_sort(arr)
print(arr)
